Fundamental Computer Concepts of Informatics
I500 - Fall 2009 - Section 7444
▪ Syllabus
▪ MATLAB on-line tutorials (includes videos and various university authorized tutorials)
▪ Template for lecture notes: download here.
▪ Midterm exam: Week 9, Thursday!!!
▪ Final exam: December 17, 5:00pm-7:00pm, I2 122
Week 1: August 31-September 4, 2009
Topics
Introduction to the course
Insertion sort and merge sort: algorithms and analysis of complexity
Matlab tutorial (lab)
Reading material
Textbook: Foundations (chapter 1, sections 1.1-1.2)
Textbook: Getting started (chapter 2, sections 2.1-2.3)
(Lecture Notes Tue) (Lecture Notes Thu)
Week 2: September 7-11 , 2009
Topics
Polynomial and matrix multiplication
Master theorem
Reading material
Textbook: Polynomials and the FFT (chapter 30, section 30.1)
Textbook: Matrix operations (chapter 28, sections 28.1-28.2)
Textbook: Recurrences (chapter 4, sections 4.1-4.3)
(Lecture Notes Tue) (Lecture Notes Thu) (Homework Assignment 1) (Data for HW 1)
Week 3: September 14-18 , 2009
Topics
Growth of functions
Reading material
Textbook: Growth of functions (chapter 3, sections 3.1-3.2)
(Lecture Notes Tue) (Lecture Notes Thu)
Week 4: September 21-25 , 2009
Topics
Probabilistic analysis of algorithms
Elementary data structures
Reading material
Textbook: Probabilistic analysis and randomized algorithms (chapter 5, sections 5.1-5.4)
Textbook: Elementary data structures (chapter 10, sections 10.1-10.4)
(Lecture Notes Tue) (Lecture Notes Thu - not available)
Week 5: September 28-October 2, 2009
Topics
Elementary data structures
Hash tables
Reading material
Textbook: Elementary data structures (chapter 10, sections 10.1-10.4)
Textbook: Hash tables (chapter 11, sections 11.3-11.4)
(Lecture Notes Tue) (Lecture Notes Thu) (Homework Assignment 2)
Week 6: October 5-9, 2009
Topics
Hash tables
Heaps
Reading material
Textbook: Heapsort (chapter 6, sections 6.1-6.5)
(Lecture Notes Tue) (Lecture Notes Thu)
Week 7: October 12-16, 2009
Topics
Binary Search Trees
Quicksort algorithm
Reading material
Textbook: Binary search trees (chapter 12, sections 12.1-12.3)
Textbook: Quicksort (chapter 7, sections 7.1-7.3)
Textbook: Sorting in linear time (chapter 8, section 8.1) - homework reading
(Lecture Notes Tue) (Lecture Notes Thu) (Homework Assignment 3) (Data for HW 3)
Week 8: October 19-23, 2009
Topics
Order statistics
Reading material
Textbook: Medians and order statistics (chapter 9, sections 9.1-9.3)
Week 9: October 26-30, 2009
Topics
Strings and languages
Midterm Exam (Thursday)
Reading material
Denning et al.: Formal grammars (chapter 3)
Week 10: November 2-6, 2009
Topics
Chomsky hierarchy of formal languages
Finite automata
Reading material
Denning et al.: Formal grammars (chapters 3-4)
(Lecture Notes Tue) (Lecture Notes Thu)
Week 11: November 9-13, 2009
Topics
Finite automata and regular expressions
String matching algorithms
Reading material
Denning et al.: Formal grammars (chapters 4-5)
Textbook: String matching (chapter 32, sections 32.1-32.2)
(Lecture Notes Tue) (Lecture Notes Thu) (Homework Assignment #4)
Week 12: November 16-20, 2009
Topics
String matching algorithms
Dynamic programming
Reading material
Textbook: String matching (chapter 32, sections 32.3-32.4)
Textbook: Dynamic programming (chapter 15, sections 15.2-15.4)
(Lecture Notes Tue) (Lecture Notes Thu)
Week 13: November 23-27, 2009
Topics
Dynamic programming
Reading material
Textbook: Dynamic programming (chapter 15, sections 15.2-15.4)
(Lecture Notes Tue)
Last updated: 11/22/2009 11:48 AM