CSCE 489 Special Topics: Problem Solving Programming Strategies
Spring 2019

Instructor: Dr. John Keyser

Office:HRBB 527C
Phone:(979) 458-0167
Email:keyser@cse.tamu.edu
Web:http://faculty.cse.tamu.edu/keyser/
Office hours:W, F 1:30-2:30, or by appointment.

Assistant: Giovanna Kobus

Office:TBD
Email:kobusgiovannaat gmaildotcom
Office hours:TBD

Important Resources

Syllabus

Academic Honesty Presentation

Acknowledgement Form

Honors Section Information

Textbook available in:

Schedule

Future dates are tentative, and will be adjusted as we see how the course develops.
Day Topics Slides Book Sections Problem Set assigned
1 Mon. Jan. 14 Course Introduction Introduction
Academic Honesty
Chapter 1 Problem set 00, Acknowlegement Form
2 Wed. Jan. 16 Basics of Competitive Problem Solving
Basic Data Structures
Basics Sections 1.2-1.3.2, 2.1-2.3
Lab 1 Fri. Jan. 18 Individual Problem set - warmup Session 01, Problem Set 01
3 Wed. Jan. 23 Basic Data Structures Basic Data Structures
Lab 2 Fri. Jan. 25 Individual Problem set Session 02, Problem Set 02
4 Mon. Jan. 28 Disjoint Sets (Union-Find) Disjoint Sets Section 2.4.2
5 Wed. Jan. 30 Range Searches: Segment Trees, Fenwick Trees Range Searches Section 2.4.3
Lab 3 Fri. Feb. 1 Individual Problem set Session 03, Problem Set 03
6 Mon. Feb. 3 Review of Problem Set 2, Lab 3
Fenwick Tree Examples
7 Wed. Feb. 6 Brute Force Approaches Brute Force Section 3.2
Lab 4 Fri. Feb. 8 Team Problem set Session 04, Problem Set 04
8 Mon. Feb. 11 Review of Problem Set 3, Lab 4
Coding the 8-queens problem
9 Wed. Feb. 13 Greedy Algorithms Survey Summary
Greedy Approaches
Section 3.4
Lab 5 Fri. Feb. 15 Individual Problem Set Session 05, Problem Set 05
10 Mon. Feb. 18 Review of Problem Set 04 and Lab 05
11 Wed. Feb. 20 Dynamic Programming Dynamic Programming Section 3.5
Lab 6 Fri. Feb. 22 Individual Problem set Session 06, Problem Set 06
12 Mon. Feb. 25 Review of Problem Set 05 and Lab 06
13 Wed. Feb. 27 Divide-and-Conquer; Binary and Ternary search Binary and Ternary Search Section 3.3
Lab 7 Fri. Mar. 1 Team Problem set Session 07, Problem Set 07
14 Mon. Mar. 4 Review of Problem Set 06
15 Wed. Mar. 6 Graph Representations
Breadth-First and Depth-First Search
Graph Introduction Sections 2.4.2, 4.1 - 4.2.2
Fri. Mar. 8 No lab today due to Spring Break Problem Set 08
SPRING BREAK
16 Mon. Mar. 18 Review of Problem Set 07
Coding example for BFS on a grid-based graph
17 Wed. Mar. 20 Connected Components, Flood Fill, Topological Sort, Bipartite (2-colored) Graphs, DFS Augmentation
Minimum Spanning Tree
Graph Algorithms
Minimum Spanning Tree
Sections 4.2.3 - 4.2.7
Lab 8 Fri. Mar. 22 Individual Problem set Session 08, Problem Set 09
18 Mon. Mar. 25 Review of Problem Set 08 and Lab 08
Bridges and Articulation Points
Bridges and Articulation Points Section 4.2.8
19 Wed. Mar. 27 Strongly Connected Components
Shortest Path Algorithms
Strongly Connected Components
Shortest Path Algorithms
Sections 4.2.9, 4.4, 4.5
Lab 9 Fri. Mar. 29 Individual Problem Set Session 09, Problem Set 10
20 Mon. Apr. 1 Review of Prooblem Set 9 and Lab 9
21 Wed. Apr. 3 Max Flow
Other Graphs
Flow Algorithms Section 4.6
Lab 10 Fri. Apr. 5 Team Problem set Session 10, Problem Set 11
- Sat. April 6 Team Competition (open; not required)
22 Mon. Apr. 8 Review of Problem Set 10 and Lab 10 Special Graphs Section 4.7
23 Wed. Apr. 10 String Algorithms Basic Strings
String Suffix Structures
Chapter 6
Lab 11 Fri. Apr. 12 Individual Problem set Session 11, Problem Set 12
24 Mon. Apr. 15 Review of Problem Set 11 and Lab 11
25 Wed. Apr. 17 Math Topics (Sequences, Modulus, CRT) Math Introduction Chapter 5
Fri. Apr. 19 NO LAB - READING DAY Problem Set 13
26 Mon. Apr. 22 Review of Problem Set 12
Math Topics (Primes, GCD, Cycles)
More Math Algorithms
27 Wed. Apr. 24 Geometry Problems Geometry Problems Chapter 7
Lab 12 Fri. Apr. 26 Individual Problem set Session 12, Problem Set 14
28 Mon. Apr. 29 Review of Problem Set 13 and Lab 12
Lab 13 Tue. April 30 Team Problem set Session 13
- Mon. May 6 FINAL EXAM TIME
10:30-12:30
Upsolve Deadline for All Problems

Problem Sets and Labs

Problem Sets

Note that some problems, designated as "Problem for Honors to Skip" are not assigned to those students in the honors section of the class. The "Challenge" problems, when given, will be somewhat more challenging problems from the set. They will be assigned and available for extra credit and for upsolving, but will not contribute to the base number for the set.
Set Number Problems Included Base Number of Problems Due Date Problem for Honors to Skip "Challenge" problem
00 Hello World!
Solving for Carrots
ACM Contest Scoring
3 1/18/19 none none
01 Backspace
Flexible Spaces
Natrij
Path Tracing
Pivot
5 1/26/19 none Kindergarten Excursion
02 Adding Words
I Can Guess the Data Structure!
Integer Lists
Pizza Hawaii
Sort of Sorting
Stogovi
Union-Find
6 2/2/19 Adding Words Stogovi
03 Association for Control Over Minds
Movie Collection
Number Sets (Hard)
Select Group
Supercomputer
Where's My Internet?
5 2/9/19 Select Group Number Sets (Hard)
04 Cow Crane
Equal Sums (Easy)
Falling Mugs
Holey N-Queens (Batman)
Perfect Pth Powers
VivoParc
5 2/16/19 Falling Mugs Perfect Pth Powers
05 Bank Queue
Coloring Socks
Postal Delivery
Watering Grass
Virus Replication
4 2/23/19 Coloring Socks Watering Grass
06 A Question of Ingestion
Bachet's Game
Narrow Art Gallery
Nikola
Restaurant Orders
4 3/2/19 Narrow Art Gallery A Question of Ingestion
07 Assembly Line
Cent Savings
Closest Sums
Room Painting
Counting Subsequences (Hard)
Trick or Treat
5 3/16/19 Counting Subsequences (Hard) Assembly Line
08 Breaking Bad
Dominoes 2
Elegant Showroom
Jailbreak
Torn 2 Pieces
4 3/23/19 none Jailbreak
09 10 Kinds of People
A Feast For Cats
Brexit
Build Dependencies
Coast Length
Treasure Hunt
5 3/30/19 10 Kinds of People Treasure Hunt
10 Birthday Party
Cantina of Babel
Get Shorty
Human Cannonball Run
Proving Equivalences
Reversing Roads
5 4/6/19 Human Cannonball Run Proving Equivalences
11 Avoiding the Apocalypse
Councilling
Gopher II
Surely You Congest
3 4/13/19 none Surely You Congest
12 Bing It On
Boggle
Dvaput
Scrolling Sign
Stammering Aliens
4 4/20/19 Scrolling Sign Stammering Aliens
13 A Vicious Pikeman (Easy)
A Vicious Pikeman (Hard)
Character Development
Fleecing the Raffle
Prime Reduction
4 4/27/19 Character Development A Vicious Pikeman (Hard)
14 Amsterdam Distance
Cutting Corners
White Water Rafting
Simple Polygon
3D Printer
4 5/4/19 none 3D Printer

Labs

Lab Number Problems Included Type Base Number of Problems Date
01 Autori
Nasty Hacks
Trik
Erase Securely
Event Planning
Bus Numbers
Bus Numbers
Are You Listening?
Individual 5 1/18/19
02 Beekeeper
Birds on a Wire
Opening Ceremony
Friday the 13th
Phone List
Working at the Restaurant
Popular Vote
Individual 4 1/25/19
03 Cookie Selection
Deduplicating Files
A Different Problem
Grandpa Bernie
Snapper Chain (Hard)
Virtual Friends
Warehouse
Individual 4 2/1/19
04 Abandoned Animal
Almost Union-Find
Ants
Boss Battle
A Classy Problem
Game Rank
Money Matters
Team 4 2/8/19
05 4 Thought
Awkward Party
Best Relay Team
Compound Words
Kastenlauf
Peg Solitaire
Lifting Walls
Individual 5 2/15/19
06 Collatz Conjecture
DVDs
Firefly
Minimum Scalar Product
Shopaholic
Skocimis
Symmetric Order
Individual 5 2/22/19
07 Distributing Ballot Boxes
Black Friday
What's On the Grille?
I Wanna Be the Very Best
Neighborhood Watch
Power Eggs
The Trip, 2007
Team 4 3/1/19
08 Appalling Architecture
Conformity
H-Index
Mia
Mr. Plow King
Toilet Seat
Train Sorting
Individual 5 3/22/19
09 All Just a Dream
Driving Range
Getting Gold
Judging Troubles
Treasure Hunt
Relocation
Zebras and Ocelots
Individual 5 3/29/19
10 A1 Paper
Paradox With Averages (Hard)
Block Crusher
Lawn Mower
Lucky Numbers
Pick Up Sticks
Znanstvenik
Team 3 4/5/19
11 Battle Simulation
CD
Radio Commercials
Dungeon Master
Fractional Lotion
Biased Standings
Sylvester Construction
Individual 5 4/12/19
12 Ocean's Anti-11
Ocean's Anti-11 (Hard)
Chanukah Challenge
Dyslectionary
Fire!
Goldbach's Conjecture
Small Schedule
Individual 5 4/26/19
13 Billiard
Card Hand Sorting
Magic Checkerboard
Counting Triangles
What Does It Mean?
Logo
A Rational Sequence
Vacuumba
Team 3 4/30/19

Resources

The following may be useful links.

Links specific to the class:

General programming contest links:

Acknowledgement

Some of the slide sets were developed by following the programming course offered by Bjarki ┴g˙st Gu­mundsson at Reykjavik University.