Location: ROME 459

Schedule: Tuesday, Thursday, 5:00pm-6:15pm

Instructor: Poorvi Vora, poorvi@gwu.edu, 706 Philips Hall. Office Hours: Tues: 1:30-4:30 pm; Thurs: 11:30-2:30 pm.

TA: Ben Hosp, bhosp@gwu.edu. Office Hours: Mon: 10-1, Wed: 12-3, in Academic Center 724.

Text: None. Class Notes.

Course Content: Complex Numbers, Linear Algebra and Matrices, Polynomial Multiplication and Discrete Convolution, Discrete Fourier Transform, Fast Fourier Transform as an algorithm for fast polynomial multiplication, Algorithmic Number Theory, with applications to media compression, audio-video processing and computer security

Prerequisites: CSci 123 (Discrete Structures I) or equivalent discrete mathematics, Math 31 or single-variable calculus

Grading: HWs (25%); best 8 of 12 quizzes (25%), two tests (25% each). HWs are due by 6 pm on the due date. Late HWs are not allowed.

297 and 124 will be graded separately. If you are an undergrad, please consult your adviser before choosing to take 297; graduate credit for 297 is not automatic for undergrads, but all those enrolled in 297 will be graded together.

Course Outline

Slides and notes on this website are not in final form till one week after the lecture covering the material. I often update notes and slides during and after the lecture

Planned Schedule

Module I: Complex Numbers. Class notes. Suggestions for further reading: 1. David E. Joyce. Dave's Short Course on Complex Numbers 2. Johan Claeys. An introduction to complex numbers 3. Kim Peppard. College Algebra Tutorial 12: Complex Numbers
5 September 2006, Lecture 1: Course Outline, Complex Numbers: Motivation, Algebraic Operations. Sections 1 and 2 from notes. Assignment for next class: revise trigonometric functions, for example,from website: http://math.usask.ca/emr/menu_trig.html.	7 September 2006, Lecture 2: Complex Numbers: Polar Representation. Section 3.1 from notes. Quiz 1
12 September 2006, Lecture 3: Complex Numbers: Powers; Section 3.2 from notes (corrected for error noted in example). No HW assigned.	14 September 2006, Lecture 4: Complete Complex Numbers; De Moivre's Theorem and roots of unity. Section 3.3 from notes Final Version: Error in Argand Diagram corrected Sept. 20. Quiz 2
Module II: Linear Equations. Suggestions for further reading: Gilbert Strang. Introduction to Linear Algebra, 3rd Edition. Wellesley-Cambridge Press.
19 September 2006, Lecture 5: Linear equations. Gaussian Elimination. From Class Handout and Notes. Practice Exercises, Complex Numbers Now with solutions, Sept. 20 HW 1 assigned. Due September 26 in Class	21 September 2006, Lecture 6: Algorithm for Gaussian Elimination. Examples. From Notes. With some modifications and updated 24 September Quiz 3
26 September 2006, Lecture 7: Gauss-Jordan Algorithm for Matrix Inverse. Determinants. Cramer's Rule for Solving Linear Equations From Notes. HW 1 Due	28 September 2006, Lecture 8: Problems on: Gauss-Jordan Inversion, Determinants, Cramer's Rule. Problems and Solutions Put here on October 4 Quiz 4
Module III: Vector Spaces. Suggestions for further reading: Gilbert Strang. Introduction to Linear Algebra, 3rd Edition. Wellesley-Cambridge Press.
3 October 2006, Lecture 9: Vector Spaces: Definition, Examples, Linear Independence From Notes.	5 October 2006, Lecture 10: Subspaces. From Notes. Updated 8 October HW 2 assigned. Due 12 October Quiz 5
10 October 2006, Lecture 11: Linear combinations and bases.	12 October 2006, Lecture 12: Eigenvalues and Eigenvectors. Quiz 6 NotesUpdated: Oct. 13
17 October 2006, Lecture 13: Norms	19 October 2006, Lecture 14: Test 1. On material covered in Lectures 1-12.
Module IV: Matlab, orthogonality. Suggestions for further reading: Matlab Tutorial by MathWorks MathWorks documentation on Matrices and Arrays Image Processing Toolbox User's Guide (HUGE!) MathWorks' web-based documentation on the Image Processing Toolbox
24 October 2006, Lecture 15: Some applications of eigenvalues.	26 October 2006, Lecture 16: Matlab tutorial (updated 10:35 am, October 26, Thursday). HW 3 assigned (updated 10:35 am, October 26, Thursday). Due 7 November, 6 pm, on Blackboard Some audio clips: Expectopatronum, Goblin, Kramer Quiz 7 Today's class will be held in Tompkins Hall, Room 405.
31 October 2006, Lecture 17: Orthogonality and Inner Products.	2 November 2006, Lecture 18: Orthogonality and Inner Products Completed Notes
Module V: Groups, Modular Arithmetic. Suggestions for further reading: MIT Open Courseware Notes, Number Theory Thomas H. Barr. Invitation to Cryptology. Prentice Hall.
7 November 2006, Lecture 19: Shift and Affine Ciphers, Modular Arithmetic. Notes HW 4 assigned. Due 16 November, 6 pm, on Blackboard	9 November 2006, Lecture 20: Modular Arithmetic, some proofs Quiz 9
14 November 2006, Lecture 21: Complete Modular Arithmetic. Notes; Groups: Definitions and Examples. Notes Both sets of notes updated 15 November 2006 HW 4 deadline changed to 17 November, 6 pm, on Blackboard	16 November 2006, Lecture 22: Multiplicative Invertibility modulo m Quiz 10
21 November 2006, Lecture 23: GCD and Euclidean Algorithm Notes. HW 5 assigned. Due 4 December 2006, by 6 pm in instructor's mailbox.	23 November 2006 Thanksgiving
28 November 2006, Lecture 24: GCD and Euclidean Algorithm. Complete	30 November 2006, Lecture 25: Euclidean algorithm for inverse. Fast Exponentiation. Notes HW 6 (extra credit) assigned. Due December 8 Quiz 11 GCD Practice Examples Solutions
5 December 2006, Lecture 26: Catch Up. Modular Inverse Practice Examples and Solutions	7 December 2006, Lecture 27: Test 2. Material: Module V: Lectures 19 through 25 inclusive.
The Students' Thoughts on this Class: Ah! Discrete Structures! Oh my god! Another proof! Die a bit inside Discrete Structures II is fun It makes your motor run Usually in circles Because the work is never done!