ECE 608

Computational Models and Methods

Professor:
Office:
Phone:
Office hours:
Login:

Arif Ghafoor
MSEE 236
4-0638
Tu, Thur 4:30pm-5:30pm or by appointment
ghafoor@purdue.edu

TA:

Office:

Office hours:

Nadra Guizani, nguizani@purdue.edu

EE208

M,W 10:00am - Noon

 

Communication

Please use email if you can’t make my office hours.

Textbook

Introduction to Algorithms (Second/Third Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press and McGraw-Hill.

Lectures

Days: Tu,Thur
Time: 3:00pm -- 4:15 pm
Room: EE117

Handouts

Lecture notes and any relevant auxiliary material will be made available in PDF format on this webpage prior to the lecture. The following handouts can only be accessed from purdue.edu. To browse the pages from off-campus, please follow this link to set up VPN on your computer.

Dynamic Programming Examples: pdf

Exams

There will be two midterm exams and one final exam. Midterm exam dates will be announced later on.

Sample Midterm I Exam:  pdf

Sample Midterm II Exam:  pdf

Solution to Quiz 1: pdf

Solution to Mid-term 1: pdf

Solution to Mid-term 2: pdf

Re-grade Request Form for Mid-term 1 (Due Date:  In class, March 27, 2014): pdf

Second Makeup Class: Tue 04/08, 2014,  6:00p – 7:15p,  Room: EE 270

Solution to Quiz 2: pdf

Final Exam (comprehensive): Wednesday, May 7, 2014, Room EE270, 8:00am – 10:00am

Grade Distribution:

5% Quizzes, 25% for each midterm exam, 45% for the final exam.

Approximate Outline

(Note, chapters marked (++) below are part of the Ph.D. qualifying exam reading list.)

Week

Chapters

Topic

Week 1

Chapter 1,2++

Administrivia, Background, and Introduction

Week 2

Chapter 2++, 3++

Asymptotics

Week 3

Chapter 3++, Appendix A, Chapter 4++

Asymptotics, Summations, Recurrences

Week 4

Chapter 4++, Chapter 28.2, Chapter 5++

Recurrences, Master Theorem, Probabilistic Analysis, Randomized Algorithms

Week 5

Chapter 6++, 7++

Sorting

Week 6

Chapters 7++, 8++

Sorting

Week 7

Chapters 8++, 9

Linear time sort, Order Statistics

Week 8

Chapter 9

Order Statistics

Week 9

Chapters 10 and 11++

Searching, Hashing

Week 10

Chapters 12++

Binary Search Trees

Week 11

Chapters 15++ and 16++

Dynamic Programming and Greedy Algorithms

Week 12

Chapters 22++

Graph Algorithms

Week 13

Chapters 23++ and 24++

Spanning Trees, Shortest Path Algorithms

Week 14

Chapters 25++ and 26

Shortest Path Algorithms, Maximum Flow

Week 15

Chapters 34++

NP Completeness

Week 16

Chapter 35

Approximation Algorithms, Review

Homeworks and Homework Solutions

Homework assignments and solutions will be posted here when assigned.

NOTE: HOMEWORKS WILL NOT BE COLLECTED FOR GRADING. HOWEVER, YOU ARE STRONGLY ADVISED TO DO YOUR HOMEWORKS ON-TIME AND CONSULT THEIR SOLUTION FOR FURTHER CLARIFICATION OF CONCEPTS.

 

Note:  Problems are assigned from the Second Edition of the text. The mapping of problems from the second to the third edition can be found here: pdf

 

Title

Handout

Solution Posting Date

Solution

Homework 1

pdf

January 23

pdf

Homework 2

pdf

January 29

pdf

Homework 3

pdf

February 4

pdf

Homework 3B

pdf

February 10

pdf

Homework 4

pdf

February 13

pdf

Homework 5

pdf

February 18

pdf

Homework 6

pdf

February 27

pdf

Homework 7

pdf

March 4

pdf

Homework 8

pdf

March 13

pdf

Homework 9

pdf

March 27

pdf

Homework 10

pdf

April 1

pdf

Homework 11

pdf

April 7

pdf

Homework 12

pdf

April 14

pdf