CSCE 430 Problem Solving Programming Strategies
Spring 2020

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:T, R 1:30-2:30 or by appointment.

Assistant: Tanner Hoke

Office:EABB Common TA area
Email:hoke_tat tamudotedu
Office hours:M, W 4:00-5:30

Assistant: Presley Graham

Office:EABB Common TA area
Email:presley.grahamat tamudotedu
Office hours:W, F 10:00-11:30

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. 13 Course Introduction Introduction
Academic Honesty
Chapter 1 Problem set 00, Acknowlegement Form
2 Wed. Jan. 15 Basics of Competitive Problem Solving
Basic Data Structures
Basics Sections 1.2-1.3.2, 2.1-2.3
Lab 1 Fri. Jan. 17 Individual Problem set - warmup Lab 01, Problem Set 01
Mon. Jan. 20 No class - MLK Day
3 Wed. Jan. 22 Basic Data Structures Basic Data Structures
Lab 2 Fri. Jan. 24 Individual Problem set Lab 02, Problem Set 02
4 Mon. Jan. 27 Union-Find (Disjoint Sets) Disjoint Sets Section 2.4.2
5 Wed. Jan. 29 Range Operations (Segment Trees, Fenwick Trees) Range Operations Section 2.4.3
Lab 3 Fri. Jan. 31 Individual Problem set Lab 03, Problem Set 03
6 Mon. Feb. 3 Problem Review
Fenwick Trees
7 Wed. Feb. 5 Brute Force / Complete Search with Backtracking Brute Force Section 3.3
Lab 4 Fri. Feb. 7 Team Problem set Lab 04, Problem Set 04
8 Mon. Feb. 10 Problem Review
N-queens coding example
9 Wed. Feb. 12 Greedy Algorithms Greedy Algorithms Section 3.4
Lab 5 Fri. Feb. 14 Individual Problem Set Lab 05, Problem Set 05
10 Mon. Feb. 17 Dynamic Programming Problems Dynamic Programming Section 3.5.1
11 Wed. Feb. 19 No class; videos instead
Lab 6 Fri. Feb. 21 No lab this day. Problem Set 06
12 Mon. Feb. 24 Problem review
DP examples (more)
Section 3.5.2
13 Wed. Feb. 26 Divide and Conquer, Binary and Ternary Search Binary and Ternary Search Setion 3.3
Lab 7 Fri. Feb. 28 Team Problem set Lab 07, Problem Set 07
14 Mon. Mar. 2 More review of DP problems
15 Wed. Mar. 4 Graph representation
Graph search applications
Graph Introduction
Graph Search Applications
Sections 2.4.2, 4.1-4.2.6
Lab 8 Fri. Mar. 6 No lab today due to Spring Break Problem Set 08
SPRING BREAK
Mon. Mar. 16 CLASS CANCELLED
covid-19
Wed. Mar. 18 CLASS CANCELLED
covid-19
Lab 9 Fri. Mar. 20 LAB CANCELLED
covid-19
16 Mon. Mar. 23 Graphs - Review of Search, Minimum Spanning Tree Minimum Spanning Tree Review 4.2.1-4.2.6 (discussion)
Section 4.3
17 Wed. Mar. 25 Graphs - Bridges and Articulation Points, Strongly Connected Components Bridges and Articulation Points
Strongly Connected Components
Sections 4.2.8-4.2.9
Lab 10 Fri. Mar. 27 Individual Problem Set Lab 10, Problem Set 09
18 Mon. Mar. 30 Graphs - Shortest Path Shortest Paths Sections 4.4-4.5
19 Wed. Apr. 1 Graphs - Max Flow algorithm, implementation, problem mapping Max Flow
Using Max Flow and other graph applications
Section 4.6
Lab 11 Fri. Apr. 3 Indvididual Problem set Lab 11, Problem Set 10
20 Mon. Apr. 6 Strings
Knuth-Morris-Pratt Algorithm
Knuth-Morris-Pratt Algorithm Sections 6.1-6.4
21 Wed. Apr. 8 Dynamic Programming on Strings (edit distance, LCS)
Tries, Suffix Trees, and Suffix Arrays
Edit Distance and Longest Common Subsequence
Tries, Suffix Trees, and Suffix Arrays
Sections 6.5, 6.6
Fri. Apr. 10 NO LAB - READING DAY Problem Set 11
22 Mon. Apr. 13 Math Intro: Number Sequences, Combinatorics Math Basics, Combinations, and Number Sequences Sections 5.1, 5.2, 5.4, 5.7
23 Wed. Apr. 15 Math: Modulus, Prime Numbers, GCD, Extended Euclid's Algorithm and Applications Math: Modulus, Primes, Extended Euclid's Algorithm and Applications Sections 5.3, 5.5, 5.6
Lab 12 Fri. Apr. 17 Individual Problem Set Lab 12, Problem Set 12
24 Mon. Apr. 20 Math: Cycle Finding and Game Analysis Math: Cycle Finding and Game Playing Sections 5.7, 5.8
25 Wed. Apr. 22 Geometry: Fundamental Geometric Operations Geometry: Points, Lines, Polygons Chapter 7 through 7.3.5
Lab 13 Fri. Apr. 24 Individual Problem set Lab 13, Problem Set 13
26 Mon. Apr. 27 Geometry: Convex Hull Geometry: Convex Hull Section 7.3.7
Lab 14 Tue. April 28 IndividualProblem set Lab 14
- Mon. May 4 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/17/20 none none
01 Flexible Spaces
Kindergarten Excursion
Musical Chairs
Natrij
Path Tracing
Pivot
5 1/25/19 none Kindergarten Excursion
02 A Classy Problem
Baloni
Distributing Ballot Boxes
I Can Guess the Data Structure!
Pizza Hawaii
Stogovi
5 2/1/20 Distributing Ballot Boxes Stogovi
03 Almost Union-Find
Association for Control Over Minds
Just For Sidekicks
Money Matters
Sheba's Amoebas
Supercomputer
5 2/8/20 Money Matters Almost Union-Find
04 Bus Numbers
Collecting Beepers
Fractional Lotion
Knights in Fen
Magic Checkerboard
Vivoparc
5 2/15/20 Fractional Lotion Magic Checkerboard
05 Bank Queue
Coloring Socks
Daydreaming Stockbroker
Tomography
Virus Replication
Watering Grass
5 2/23/20 Coloring Socks Watering Grass
06 A Question of Ingestion
Narrow Art Gallery
Nikola
Radio Commercials
The Uxuhul Voting System
4 2/29/20 Narrow Art Gallery A Question of Ingestion
07 Assembly Line
Freight Train
Just Passing Through
Spiderman's Workout
Trick or Treat
4 3/23/20
12:01 a.m.
Spiderman's Workout Assembly Line
08 Breaking Bad
Dominoes 2
Association of Cats and Magical Lights
Elegant Showroom
Torn 2 Pieces
4 3/28/20 None Association of Cats and Magical Lights
09 A Feast for Cats
Birthday Party
Build Dependencies
Cantina of Babel
Get Shorty
Proving Equivalences
5 4/4/20 None Proving Equivalences
10 Avoiding the Apocalypse
Surely you Congest
Councilling
Gopher II
Reversing Roads
3 4/11/20 Gopher II Councilling
Surely You Congest
11 Bing It On
Boggle
Dvaput
Prince and Princess
Stammering Aliens
4 4/18/20 Boggle Stammering Aliens
12 A Vicious Pikeman (easy)
A Vicious Pikeman (hard)
Candy Distribution
Locked Treasure
Prime Reduction
4 4/25/20 A Vicious Pikeman (easy) A Vicious Pikeman (hard)
13 TBD TBD TBD TBD TBD

Labs

Lab Number Problems Included Type Base Number of Problems Date
01 Odd Man Out
Railroad
Mars Window
Bus Numbers
Backspace
Thanos the Hero
Disastrous Downtime
Individual 4 1/17/20
02 Abandoned Animal
Biased Standings
Birds on a Wire
Dice Cup
Doorman
Missing Numbers
Paradox with Averages (Hard)
Room Painting
Individual 4 1/24/20
03 Administrative Difficulties
Army Strength (Hard)
Cookie Selection
Hay Points
Symmetric Order
What's On the Grille?
Zagrade
Individual 4 1/31/20
04 Another Brick in the Wall
Ants
Are You Listening?
Game Rank
Kastenlauf
Neighborhood Watch
Snapper Chain (Hard)
Working at the Restaurant
Team 4 2/7/20
05 Almost Perfect
Ferry Loading IV
Lifting Walls
Opening Ceremony
Planting Trees
Warehouse
Zamka
Antiarithmetic?
Individual 5 2/14/20
06 lab cancelled - Prof & TAs travel 2/21/20
07 Font
House of Cards
Left and Right
Mia
Power Eggs
A Rational Sequence
Reversed Binary Numbers
Turbo
Team 4 2/28/20
08 lab cancelled - Spring Break 3/6/20
09 lab cancelled - covid-19 3/20/20
10 Adding Words
Bachet's Game
Boss Battle
Falling Mugs
Getting Gold
Peg Solitaire
Semafori
Virtual Friends
Individual 4 3/27/20
11 Counting Subsequences (Hard)
Driving Range
Jailbreak
Judging Troubles
Rock Paper Scissors Tournament
Secret Message
Take Two Stones
What Does It Mean?
Individual 5 4/3/20
12 10 Kinds of People
Arctic Network
Beekeeper
Exact Change
Firefly
Lawn Mower
Retribution
Treasure Hunt
Individual 4 4/17/20
13 TBD Individual TBD 4/24/20
14 TBD Individual TBD 4/28/20

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.