ECE G205, Fundamentals of Computer Engineering

Fall 2003

The class meets Monday and Wednesday from 9:50am to 11:30am in 410 Ell

Instructor:

        Stefano Basagni
        Office: Dana 312
        Office hours: Wednesday, from 2:30pm to 4:30pm.
        Telephone: 617 373 3061
        E-mail: basagni@ece.neu.edu

Teaching Assistant:

        Stephen Frechette
         E-mail: sfrechet@ece.neu.edu


Textbook: (1) Introduction to Algorithms, second edition, T. H. Cormen et al., McGraw-Hill, 2001. (2) C++, How to Program, fourth edition, H. M. Deitel and P. J. Deitel, Prentice Hall, 2002. (3) Notes from the Instructor.


Course Objectives: The aim of the course is to teach the basic of data structures and fundamental algorithms described by using a common programming language such as C++. The better understanding of data structure and basic algorithms should lead to program optimization, especially from a time complexity point of view.


Topics: Computational problems and algorithms. From algorithms to programs. Measuring program efficiency: Time complexity and space complexity. C++ basics and recursion. Abstract Data Types and C++ classes. Basic data structures (in C++): Arrays, pointers and structs, stack and queues, linked lists. Fundamentals of searching and sorting. More complex data structures: Trees and graphs and related algorithms.


Evaluation: There will be homework, one midterm and one final exam.

Grades: Homework: 20%. Midterm: 35%. Final exam: 45%.

The grades for the class are determined from the total points as follows:

        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 22 2003. Final: Monday, December 15 2003.

Midterm and final examination policy: All examinations are open 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.)

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. Mon. Sep. 8 2003: 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. 17 2003.

2. Wed. Sep. 10 2003: 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).
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. Mon. Sep. 15 2003: 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.

4. Wed. Sep. 17 2003: Introduction to C++ Standard Template Library (STL). Download the slides of this class. Download an example of a matrix class defined by using the STL.
Assignments: Topics covered in this class can be found in any book on C++, e.g., chapter twentyone of the Deitel & Deitel book.
Homework:Download homework 2. Homework are due in class on Wed. Sep. 24 2003.

5. Mon. Sep. 22 2003: Solution recommendations for homework #1.

6. Wed. Sep. 24 2003: Sorting: Bubble Sort and Merge Sort (Divide and Conquer). Download the slides of this class.
Assignments: Read the textbook from page 27 to page 38.
Homework:Download homework 3. Homework are due in class on Wed. Oct. 1 2003.(Windows users, please, refer to the homework guidelines above for how to e-mail the executable files to the TA.)

7. Mon. Sep. 29 2003: Sorting: Time complexity of Merge Sort. Lower bounds for sorting. Sorting in linear time: Counting Sort, Radix Sort. Download the slides of this class.
Assignments: Read the textbook from page 165 to page 170.

8. Wed. Oct. 1 2003: Sorting in linear time: Radix sort. Searching and selecting elements in an array. Download the slides of this class.
Assignments: Read the textbook from page 170 to page 173 and selected topics from chapter 9.
Homework:Download homework 4. Homework are due in class on Wed. Oct. 8 2003.(Windows users, please, refer to the homework guidelines above for how to e-mail the executable files to the TA.)

9. Mon. Oct. 6 2003: Elementary data structures: Stacks, queues, lists and rooted trees. Download the slides of this class.
Assignments: Read the textbook from page 196 to page 217.

10. Wed. Oct. 8 2003: Hash Tables, basics. Download the slides of this class.
Assignments: Read the textbook, Chapter 11.
Homework:Download homework 5. Homework are due in class on Wed. Oct. 15 2003.

11. Wed. Oct. 15 2003: Binary Search Trees (BTSs). Download the slides of this class.
Assignments: Read the textbook, Chapter 12, from page 253 to page 264.
Exercises for the Midterm: Download sample problems for preparing to the midterm. Solution recommendations for the given problems will be discussed in class.

12. Mon. Oct. 20 2003: Warm-up exercises in preparation to the midterm: Solution recomendations.

13. Wed. Oct. 22 2003: Midterm. The midterm will be on all the topics covered so far in class. It will be held in 410 EL. Solution recommendations to the midterm problems are available outside the instructor's office door.

14. Mon. Oct. 27 2003: Graph representation; elementary algorithms on graphs: Breadth-First Search. Download the slides of this class.
Assignments: Read the textbook, Chapter 22, from page 524 to page 539.

15. Wed. Oct. 29 2003: Graph Depth-First Search DFS. Connected compnents. Download the slides of this class.
Assignments: Read the textbook, Chapter 22, from page 540 to page 549.
Homework:Download homework 6. Homework are due in class on Wed. Nov. 5 2003.

16. Mon. Nov. 3 2003: Minimum-Weight Spanning Tree (MST) algorithms. Download the slides of this class.
Assignments: Read the textbook, Chapter 23, from page 561 to page 574.

17. Wed. Nov. 5 2003: MST: Prim's algorithm and its complexity. Download the slides of this class.
Assignments: Read the textbook, Chapter 23, from page 561 to page 574.

18. Mon. Nov. 10 2003: Shortest Paths. Basics definitions and properties. Download the slides of this class.
Assignments: Read the textbook, Chapter 24, from page 580 to page 592.

19. Wed. Nov. 12 2003: Bellman-Ford algorithm and shortest paths on graphs. Download the slides of this class.
Assignments: Read the textbook, Chapter 24, from page 588 to page 595.
Homework:Download homework 7. Homework are due in class on Wed. Nov. 19 2003.

20. Mon. Nov. 17 2003: Shortest Paths. Dijkstra algorithm, description, correctness and analysis. Download the slides of this class.
Assignments: Read the textbook, Chapter 24, from page 595 to page 614.

21. Wed. Nov. 19 2003: Application of shortest paths algorithm to the Internet: The distributed Bellman-Ford algorithm. Guest lecturer: Prof. Chiara Petrioli, Rome University "La Sapienza." Download the slides of this class.
Assignments: You may read selected chapters from the Kurose-Ross book Computer Networking: A Top-Down Approach Featuring the Internet to which the presentation is inspired.
Homework:Download homework 8. Homework are due in class on Wed. Nov. 26 2003.

22. Mon. Nov. 24 2003: Distributed Bellman-Ford and routing over the Internet. Implementation problems and discussion.

23. Wed. Nov. 26 2003: All-Pairs Shortest Paths. Download the slides of this class.
Assignments: Read the textbook, Chapter 25, from page 620 to page 628.

24. Mon. Dec. 1 2003: All-Pairs Shortest Paths: The Floyd-Warshall algorithm. Download the slides of this class.
Assignments: Read the textbook, Chapter 25, from page 620 to page 640.

25. Wed. Dec. 3 2003: A light introduction to the Maximum Flow problem and the Ford-Fulkerson method. Download the slides of this class.
Assignments: Read the textbook, Chapter 26, from page 643 to page 664.

Mon. Dec. 8 2003: The class is cancelled. Keep warm ;-)

26. Wed. Dec. 10 2003: Review exercises for the final.

FINAL: Mon. Dec. 15 2003, 8:30am-11:30am: The final is on everything covered from the midterm onward. It will be held in 410 EL. It is a "closed-book, closed-notes" exam.

Thanks for attending Fall 2003 ECE G205!

Please, report typos, errors and decent comments to basagni@ece.neu.edu