Introduction to Computer Science      COMP 250       Fall 2018

Instructors: Michael Langer & Giulia Alberini

Lectures:       Sec. 001       MWF  10:35-11:25     MCMED 522                
Sec. 002       MWF  14:35-15:25     LEA 219


Announcements
  • For students who are not registered and would like to get in, please be patient. It happens every year that students drop the course by the end of drop/add period.
  • Students who are registered in the course should see mycourses for all announcements.
Resources
LECTURES EXERCISES (with solutions)
Preliminaries: basic math
  1. introductions (slides)
  2. grade school algorithms for arithmetic 
  3. logarithms & modular arithmetic
  4. number representations and base conversions




Exercises 1: grade school arithmetic, number representations (PDF)
Object Oriented Design in Java 1
  1. Char, unicode, primitive type casting
  2. packages, modifiers, UML
  3. inheritance
  4. inheritance and modifiers, Object class
  5. type conversion, Polymorphism, Class class



Exercises 13: object oriented design (PDF)
Linear Data Structures
  1. array lists
  2. singly linked lists 
  3.             (Mon. Oct. 1 class cancelled because of QC elections)
  4. doubly linked lists 
  5. iterative sorting algorithms   bubble, selection, & insertion sort
  6. stacks
  7. queues     + ADTs, Java API, interfaces

Exercises 2: arrays and array lists (PDF)

Exercises 3: linked lists (PDF)   (code)  

Exercises 4: iterative sorting (PDF)

Exercises 5: stacks and queues (PDF)
Object Oriented Design in Java 2
  1. interfaces, abstract classes
  2. examples of interfaces   Comparable, Iterable, Iterator
Induction and Recursion
  1. mathematical induction
  2. recursion 1   factorial & Fibonacci, reverse/sort list, Tower of Hanoi; call stack
  3. recursion 2   power, binary search
  4. recursion 3   mergesort, quicksort

Exercises 6: induction and recursion (PDF)
Non-linear Data Structures
  1. rooted trees
  2. tree traversal
  3. binary trees e.g. expression trees
  4. binary search trees
  5. priority queue, heaps 1
  6. heaps 2
  7. maps, hash codes
  8. hash maps
  9. graphs
  10. graph traversal (breadth vs depth first)

Exercises 9: trees (PDF)



Exercises 10: heaps (PDF)


Exercises 11: hashing (PDF)


Exercises 12: graphs (PDF)
Mathematical Tools for Analysis of Algorithms
  1. recurrences 1   back substitution method, examples, brief review of logarithms
  2. recurrences 2   mergesort, quicksort
  3. big O   1   analogy to limits in Calculus, formal big O definition
  4. big O   2   rules for big O, big Omega, some incorrect proofs
  5. big O   3   big Theta, best and worst case, limits rules


Exercises 7: recurrences (PDF)

Exercises 8: big O (PDF)
EXTRA
  1. why (or why not) go to grad school ?
  2. beyond COMP 250, final exam (slides)