96-100:
A;
90-95:
A-;
85-89:
B+;
80-84:
B;
75-79:
B-;
70-74:
C+;
60-69:
C;
50-59:
C-;
< 50: F.
Expected Test Dates.
Midterm: Wednesday, October 20 2004.
Final: Wednesday, December 15 2004, 1:30pm-4:30pm, 107 Robinson.
Midterm and final examination policy: All
examinations are CLOSED book and notes. All devices with communication
capabilities, including cell phones and pagers, must be
turned off during the examination. Stand-alone calculators may be
used during the examination (do not use your cell phone calculator).
Laptops or palmtops are not permitted.
Student Responsibilities: Class attendance is responsibility of each individual. If a student should elect not to attend a class, s/he is responsible for any handouts, announcements, reading material and content of missed lecture.
Scholastic dishonesty (e.g., cheating, plagiarism, collusion, record falsification, etc.) will be punished according to NU policies and standards.
Guidelines for submitting your homework: Homework are due in class on the specified date. Turn in what is completed by the deadline for partial credits. No late submission will be accepted. ("No shows" will obtain 0 points.)
ATTENTION REMOTE STUDENTS: All submissions must be typed and sent via e-mail to the TA.
If k is the total number of homework assigned, at least (int)(k/2)+1 of the homework have to be turned in for passing the class with more than a B.
All submissions must be your own work. Identical, or semi-identical assignments will not be accepted.
Only homework returned in a 9in x 12in envelope will be accepted. (If you cannot find such envelope, ask the Instructor.) Please, write your name and the class name (ECE G205) on the envelope (write clearly, please).
When questions are asked that do not require executable codes (i.e., programs code and executables) write your answer in the homework that has been handed out. You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. Be neat!
When problems are given that require executable codes (i.e., programs code and executables) a print-out of the code should be turned in by the due date to the instructor, and an e-mail should be sent to the TA containing
(a) the code (text file, .cpp), and
(b) the executable (clearly specify in the e-mail in which platform the executable runs).
The name of these files should be the FIRST LETTER of your NAME + your LAST NAME followed by the extension .cpp for the code and NO extension for the executable (e.g., sbasagni.cpp and sbasagni).
IT IS IMPORTANT that the Windows executable is ZIPPED since the ECE firewall blocks .exe files even when you remove the extension. If you do not zip the file the TA will not be able to receive it.
Download the syllabus and the homework submission guidelines in Portable Document Format (PDF)(
).
CLASSES
1. Wed. Sep. 8 2004: Introduction to ECE G205. Computational problems, algorithms and programs. Algorithm analysis and correctness. An example: Sorting and Insertion Sort. Download the slides of the first class.
Assignments: Read chapter 1 of the textbook and chapter 2 till page 27.
Homework:Download homework 1. Homework are due in class on Wed. Sep. 15 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it.
2. Mon. Sep. 13 2004: From Algorithms to Programs. Basics of C++: From the "C core" to functions. Download the slides of this class. Download an example of a simple C++ program that illustrates Insertion Sort (iterative and recursive versions). See an animation for Insertion Sort here.
Assignments: Topics covered in this class can be found in any book on C++, e.g., the first four chapters of the Deitel & Deitel book.
3. Wed. Sep. 15 2004: From Algorithms to Programs. Basics of C++: Functions, recursion, arrays, structures and classes. Download the slides of this class.
Assignments: Topics covered in this class can be found in any book on C++, e.g., chapters five and six of the Deitel & Deitel book.
Homework:Download homework 2. Homework are due in class on Wed. Sep. 22 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it.
4. Mon. Sep. 20 2004: Solution recommendations for homework 1. The C++ Standard Template Library. Download the slides of this class.
Assignments: Topics covered in this class can be found in any book on C++, e.g., the twentyfirst chapter of the Deitel & Deitel book.
5. Wed. Sep. 22 2004: More on sorting: Bubble sort. Algorithm design techniques: Divide and Conquer and Merge Sort. Download the slides of this class. Here is an animation of bubble sort. An animation that gives an idea of how "slow" Bubble Sort is can be found here.
Assignments: Read from page 27 to page 38 of the textbook.
Homework:Download homework 3. Homework are due in class on Wed. Oct. 6 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it.
6. Mon. Sep. 27 2004: Merge Sort: Analysis. Lower bound for sorting. Sorting in linear time: Counting Sort. Download the slides of this class.
Assignments: Read from page 167 to page 170 of the textbook.
7. Wed. Sep. 29 2004: Sorting in linear time: Counting sort and radix sort. Searching: i-th order statistics, min and max. Binary search. Download the slides of this class.
Assignments: Read from page 165 to page 173 and from page 183 to page 185 of the textbook.
8. Mon. Oct. 4 2004: Basics on dynamic data structures and related operations: Sets, stacks, queues, lists and trees. Download the slides of this class.
Assignments: Read from page 196 to page 217 of the textbook.
9. Wed. Oct. 6 2004: Hash tables 101. Download the slides of this class.
Assignments: Read Chapter 11 of the textbook.
Homework:Download homework 4. Homework are due in class on Wed. Oct. 13 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it.
10. Wed. Oct. 13 2004: Binary Search Trees (BTSs). Download the slides of this class.
Assignments: Read the textbook, Chapter 12, from page 253 to page 264.
11. Mon. Oct. 18 2004: Warm-up exercises in preparation to the midterm.
12. Wed. Oct. 20 2004: Midterm. The midterm will be on all the topics covered so far in class. It will be held in 107 Robinson (class usual classroom).
13. Mon. Oct. 25 2004: Solution recomendations for the problems of the midterm. Grahps 101. Basic algorithms: Breadth First Search and Depth First Search. Download the slides of this class.
Assignments: Read from page 524 to page 549 of the textbook.
Homework:Download homework 5. Homework are due in class on Mon. Nov. 8 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it. When sending the code to the TAs, please, send it to BOTH of them.
14. Wed. Oct. 27 2004: Shortest Paths: Basic properties. Download the slides of this class.
Assignments: Read from page 580 to page 592 of the textbook.
15. Mon. Nov. 1 2004: The Minimum Spanning Tree (MST) problem. Generalities, and the solutions by Kruscal and Prim. Download the slides of this class. (This class is kindly taught by Prof. Waleed Meleis.)
Assignments: Read from page 561 to page 574 of the textbook.
16. Wed. Nov. 3 2004: The Dijkstra algorithm for Single-Source Shortest-Paths. Download the slides of this class. Here you can find an animation of the Dijkstra algorithm. (This class is kindly taught by Prof. Mehdi Tahoori. It is supposed to last less than usual.)
Assignments: Read from page 595 to page 614 of the textbook.
17. Mon. Nov. 8 2004: The Bellman-Ford algorithm for Single-Source Shortest-Paths and shortest paths on DAGs. Download the slides of this class.
Assignments: Read from page 588 to page 595 of the textbook.
18. Wed. Nov. 10 2004: All-Pairs Shortest-Paths: Basics and the Floyd-Warshall Algorithm. Download the slides of this class.
Assignments: Read from page 620 to page 640 of the textbook.
Homework:Download homework 6. Homework are due in class on Wed. Nov. 17 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it.
19. Mon. Nov. 15 2004: Introduction to flow problems. Download the slides of this class.
Assignments: Read from page 643 to page 664 of the textbook.
20. Wed. Nov. 17 2004: Dynamic Programming 101. Download the slides of this class.
Assignments: Read from page 323 to page 347 of the textbook.
Homework:Download homework 7. Homework are due in class on Mon. Nov. 29 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your reply to it.
MIDTERM MAKE-UP ASSIGNMENT: This test if for all those students who have earned LESS THAN (<) 80 in the midterm. It is intended to allow them to get a maximum of 80 as their midterm grade. In particular, the grade x ≤100 earned in this assignment will be the percentage of 80-MG, i.e., of the amount they need to get an 80, where MG is the grade they had in the midterm. For example, if a student has earned a 50 (MG) in the midterm and 70 (x) in this assignment, his or her midterm grade will be 50+21=71, given that 21 is 70% of 80-50=30. Download the assignment. The test is due in class on Wed. Dec. 1 2004. It would be helpful if you could provide your solutions typed (rather than handwritten). For those who use LaTeX, you can use my own LaTeX file and add your answers to it.
21. Mon. Nov. 22 2004: Greedy algorithms. Download the slides of this class.
Assignments: Read from page 370 to page 392 of the textbook.
22. Mon. Nov. 29 2004: An application of the Bellman-Ford algorithm: Routing over the Internet. Download the slides of this class. This class is gently taught by Prof. Chiara Petrioli, of the university of Roma "La Sapienza."
23. Wed. Dec. 1 2004: Routing over the Internet. Representing networks with graphs: The special case of wireless networks. Topology generation. Download the slides of this class. Part of this class is gently taught by Prof. Chiara Petrioli, of the university of Roma "La Sapienza." (There will be no Homework # 8.)
24. Mon. Dec. 6 2004: The Maximum Independent Set problem on graphs. Greedy approximation and its application to clustering for ad hoc wireless networks. Download the slides of this class.
25. Wed. Dec. 8 2004: Warm-up exercises in preparation to the final.
Wed. Dec. 15 2004: FINAL. The final will be on all the topics covered in class from the Midterm on (graph stuff). It will be held in 107 Robinson (class usual classroom) from 1:30pm to 4:30pm.
The FINAL has been graded! I will be in the office Thursday Dec. 16th, from 3pm to 6pm. You are welcome to stop by and have a look to your final.
Thanks for attending Fall 2004 ECE G205!
Please, report typos, errors and decent comments to basagni@ece.neu.edu