BIT 265: Structures And Algorithms

Homework StudentTracker Syllabus

Welcome to BIT 265!

 

We'll be meeting twice a week in person (with no required online component)

Class meetings: Mondays and Wednesday, 1:15pm – 3:20pm, Room CC1-231

 

Schedule For The Quarter

Note that while there are no current plans to change the schedule, we may end up doing so anyways.

Lecture # Date Topic Presenters Reading Due Dates:
Self-Written
("from scratch")
Due Dates:
Use an
existing library
1 Class Orientation
AVL Trees: Insert
  Pg.296,
online materials (see below)

Notes/Talking Points
   
2  AVL Trees – Insert     Updated A1 (please include due dates)  
3  AVL Trees – Insert     A1 Due
A1 revision due date will be announced when A1 is graded
 
4 AVL Trees – Remove        
5 Workshop:
Finding and using code online
  slide show (see below)    
6 NO CLASS Non-Instructional Day      
7 Heaps, Heapsort Kevin
Sarah
2.3.2, Ch 6
Online materials
   
8 MergeSort Ethan
Emilio
2.3
Online materials
   
9 B-Trees-Overview, Add Eric
Keith
Ch 23
Online materials
NOTE: May 16th is canceled  
10 B-Trees –Delete Alex
Matt
23.2
23.3
23.4
Online materials
BIT PLACEMENT TEST  
11 Skip Lists Ben
Sarah
Ch 25
Online materials
   
12 Graphs:
Overview
Breadth-first search
Depth-first search
Kevin
Minah
Ch 26
Online materials
   
13 Graphs
Single-source Shortest Path
(Dijkstra's algorithm)
Emilio
Matt
Ch. 26
Online materials
Minah: Skip List Minah: Djikstra's Alg.
14 NO CLASS NO CLASS NO CLASS    
15 Minimum Spanning Tree
(Prim's, Kruskal's algorithms)
Eric
Ethan - BOTH Kruskals AND Prim's
Ch. 26
Online materials
   
16 Graphs: All-pairs Shortest Path
(Floyd-Warshall)
Ben
Roberto
Ch 24
Online materials
   
17 Hash Tables-
Open Addressing
Keith
Minah
Ch. 11
Online materials
   
18 Hash Tables-
Hashing With Chaining,
Good Hashing Algorithms
  Ch. 11
Online materials
   
19 Dynamic Programming Alex
Daniel
Ch. 15
Online materials
Changes to the projects  
20 Greedy Algorithms Daniel
Roberto
Ch. 16
Online materials
Minah: Greedy Minah: Dynamic
21      

BRING YOUR WORK TO CLASS
 
22 Term Project Presentations

Term Project Presentations      
ADD NEW TOPICS HERE :)

Changes to the projects

  • Due this Friday ( 5 / 7 ) at 8am:
    • One algorithm that you've implemented yourself - Be very clear what this is.
    • One algorithm that you've found code for online and used in your program - Be very clear what this is.
  • Including a 'README.txt' file would be a great way to clearly communicate which one you're using and which one you're writing yourself.
  • A 'prototype' program that demonstrates the basic ideas of how you might use the above algorithms in the context of your overall idea.  You do NOT need any sort of user interface, nor do you need to develop much of the program beyond the part that gives an idea of how you'd use the algorithm/data structure if you were to go on and finish the program.
  • All work is due on Friday, June 14th at 9am

Who's doing what

  • Ben
    • Write: Hash Table
    • Find: Dijkstra's or Heapsort
    • Car dealership product logistics program
  • Roberto
    • Write: B-Tree, AVL Tree, MergeSort
    • Find: Hash Table
    • Algorithm tutorial
  • Emilio
    • Write: BFS - finding nearby characters
    • Find: AVL Tree to store rooms
    • Idea: RPG Game
  • Keith
    • Write: AVL Tree to store history??scores
    • Find: MergeSort & SkipList
    • Idea: MarsLander
  • Ethan
    • Write: Hash tables
    • Find: MergeSort
    • Idea: Name memorizer
  • Kevin
    • Write: SkipList
    • Find: B-Tree
    • Idea: Photo organizer
  • Daniel
    • Write: Dijkstra
    • Find: Hashtable
    • Idea: Inventory organizer for D&D; will interact with DB for storage of hash table
  • Alex
    • Write: Dijkstra
    • Find: HeapSort
    • Idea: Distance finder for D&D
  • Matt
    • Write: MergeSort
    • Find: AVL Tree
    • Idea: Accounting System - clients, dates they were visited
  • Sarah
    • Write: MergeSort
    • Find: Hash Tables
    • Idea: Donation tracker
    • Write:
    • Find:
    • Idea:

Hash Tables

Floyd-Warshall: All-Pairs Shortest Path

Minimum Spanning Tree

Dijkstra's Algorithm (Single Source, Shortest Path)

Graphs, Breadth-First Search (BFS), Depth-First Search (DFS)

Skip Lists

B-Trees

MergeSort

Heapsort

AVL Trees

Instructor's Handout on AVL trees  (including both Add and Remove)
Instructor notes on AVL tree lecture (including a list of errors in the code)

Other Online resources:

Workshop: Finding and using code online

Slides

 

Notes for the instructor