ECE 1320, Optimization Methods

Winter 2003

The class meets Monday, Wednesday and Thursday from 9:15am to 10:20am in 102 KA (No longer in 233 RY or 308 HT as announced)


        Stefano Basagni
        Office: Dana 312
        Office hours: Wednesday, from 2:30pm to 4:30pm.
        Telephone: 617 373 3061

Teaching Assistant:

        Marco Elia

Textbook: (1) A Practical Introduction to Data Structures and Algorithm Analysis, second edition, C. A. Shaffer, Prentice Hall, 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 (sorting and searching) 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. Asymptotic notation. 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.

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:

        95-100: A;
        90-94: A-;
        85-89: B+;
        80-84: B;
        75-79: B-;
        70-74: C+;
        65-69: C;
        60-64: C-;
        55-59: D+;
        50-54: D;
        < 50: F.

Expected Test Dates. Midterm: Thursday February 6 2003. Final: Thursday, March 13 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 1320) 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 renamed to remove the .exe extension since the ECE firewall blocks .exe files and the TA will not be able to receive it.

Download the syllabus and the homework submission guidelines in Portable Document Format (PDF)( ).


1. Mon. Jan. 6 2003: Introduction to ECE 1320. Computational problems and algorithms.

2. Wed. Jan. 8 2003: Data Items, Data Types, Abstract Data Types and Data Structures.
Assignments: Chapter 1 of the textbook, and chapter 6 of the "D&D" book.

3. Thu. Jan. 9 2003: Program cost and asymptotic notation.
Assignments: Chapter 3 of the textbook, till page 55.
Homework:Download homework 1. Homework are due in class (hard copy) and via e-mail (to the TA) on Thu. Jan. 16 2003. For testing your functions you might want to use the following C++ files. Download homework 1 solution recommendations.

4. Mon. Jan. 13 2003: Algorithm analysys, asymptotic analysys and the big-O notation.
Assignments: Chapter 3 of the textbook, to page 61 (inclusive).

ROOM CHANGE: From Wed. Jan. 15 2003 onward the class meets in KA 102. We apologize for the confusion with the classrooms.

5. Wed. Jan. 15 2003: Big O, Big Omega and Big Theta notations, and examples.
Assignments: Complete the reading of chapter 3 of the textbook.

6. Thu. Jan. 16 2003: More examples on the Big O, notation, etc.
Assignments: Complete the reading of chapter 3 of the textbook.
Homework:Download homework 2. Homework are due in class (hard copy only this time) on Thu. Jan. 23 2003.

Mon. Jan. 20 2003: Holiday.

7. Wed. Jan. 22 2003: Big Omega and Big Theta notations. Recursion 101.
Assignments: Read chapter 2 of the textbook, from page 28 to page 41.

OFFICE HOURS on Wed. Jan. 22 2003 will be held in the SNELL Un*x Lab. (second floor Snell Eng.). You might need this file.

8. Thu. Jan. 23 2003: Recursion and worst-case time complexity.
Homework:Download homework 3. Homework are due in class and via e-mail to the TA on Thu. Jan. 30 2003.

9. Mon. Jan. 27 2003: More on recursion and worst-case time complexity of computational problems and algorithms: The "Towers of Hanoi" problems.

10. Wed. Jan. 29 2003: Review exercises on Big O notation and computational time.

11. Thu. Jan. 30 2003: Fundamental data structures: Lists. You might want to have a look at the C++ code for lists as presented in class.
Assignments: Read chapter 4 of the textbook, from page 87 to page 91 and from page 95 to page 102.
Homework:Download homework 4. Homework are due in class and via e-mail to the TA on Thu. Feb. 6 2003.

12. Mon. Feb. 3 2003: More on Lists.
Assignments: Read chapter 4 of the textbook, from page 87 to page 91 and from page 95 to page 102.

13. Wed. Feb. 5 2003: Review exercises for midterm. (Solution recommendations to homework 3.)

14. Thu. Feb. 6 2003: MIDTERM. The test will cover everything that has been seen in class so far. The midterm will be held in 130 HT (Hurtig) and not in the usual classroom.
Homework:Download homework 5. Homework are due in class and via e-mail to the TA on Thu. Feb. 13 2003.

15. Mon. Feb. 10 2003: Solutions to midterm problems and more on lists.

16. Wed. Feb. 12 2003: Lists: Remove and list creation functions.

17. Thu. Feb. 13 2003: More on lists and operations on lists.

18. Mon. Feb. 17 2003: Solutions to homework 5 problems.

19. Wed. Feb. 19 2003: Queues and stacks. Divide and Conquer 101.
Homework:Download homework 6. Homework are due in class and via e-mail to the TA on Thu. Feb. 27 2003.
Assignments: Read chapter 4 of the textbook, from page 119 to page 133.

20. Thu. Feb. 20 2003: Divide and Conquer. Sorting an array of integers (Insertion sort, Bubble sort and Merge sort.)

21. Mon. Feb. 24 2003: The complexity of Merge sort.

22. Wed. Feb. 26 2003: Lower bound for sorting, and basics on trees.

23. Thu. Feb. 27 2003: Sorting in linear time: Counting sort. Some more on trees.

24. Mon. Mar. 3 2003: Binary trees. You might want to have a look at the C++ code for trees as presented in class.

25. Wed. Mar. 5 2003: Functions and operations on binary trees.

26. Thu. Mar. 6 2003: Review exercises for the final.

27. Fri. Mar. 14 2003 @ 1PM: FINAL. The test will cover everything that has been seen in class from the midterm onward. The final will be held in 39 SL.

Thanks for attending Winter 2003 ECE 1320!

Please, report typos, errors and decent comments to