Applications Lab

Objectives

The goal of this lab is to apply some of the techniques and structures we've studied this semester. You should read the problem descriptions, determine appropriate collection types, and implement efficient solutions. You should work in groups on this lab.

DO NOT RE-INVENT THE WHEEL! None of these problems require custom data structures; they can all be implemented using either the collections we've implemented in class or built-in Python collections. You should utilize these collection implementations. Try to keep your methods under 15 lines of code.

Duplicate Tracker

Begin by downloading the following files:

Complete the methods of the DuplicateTracker class so that all operations are as efficient as possible. The purpose of this class is to process a sequence of user IDs such that duplicate IDs are identified and may be efficiently retrieved as a sorted Python list. You should assume that both the "add" and the "get" methods may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a short interaction with the DuplicateTracker class that illustrates the desired functionality: 

    >>> from duplicate_tracker import DuplicateTracker
    >>> tracker = DuplicateTracker()
    >>> tracker.add_id(5)
    >>> tracker.add_id(2)
    >>> tracker.add_id(1)
    >>> tracker.add_id(2)
    >>> tracker.add_id(5)
    >>> tracker.add_id(5)
    >>> print(tracker.get_duplicates())
    [2, 5]
    >>> tracker.add_id(1)
    >>> print(tracker.get_duplicates())
    [1, 2, 5]

You can test your implementation by executing duplicate_tests.py in the same folder as your completed solution. This script will run some tests for correctness as well as timing tests. The output of a successful test should look like the following (with the X's replaced with actual timing results): 

    Passed correctness test!
    101100 operations performed in XXX seconds.
    Average add time: XXX microseconds
    Average get time: XXX microseconds

Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Frequent Tracker

Begin by downloading the following files:

Complete the methods of the FrequentTracker class so that all operations are as efficient as possible. The purpose of this class is to process a sequence of words such that the most frequent word may be efficiently identified and retrieved at any given time. You should assume that both the "add" and the "get" methods may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a short interaction with the FrequentTracker class that illustrates the desired functionality: 

    >>> from frequent_tracker import FrequentTracker
    >>> tracker = FrequentTracker()
    >>> tracker.add_word("hello")
    >>> tracker.add_word("hello")
    >>> tracker.add_word("goodbye")
    >>> print(tracker.get_most_frequent())
    hello
    >>> tracker.add_word("goodbye")
    >>> tracker.add_word("goodbye")
    >>> print(tracker.get_most_frequent())
    goodbye

You can test your implementation by executing frequent_tests.py in the same folder as your completed solution. This script will run some tests for correctness as well as timing tests. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Job Sequencer

Begin by downloading the following files:

Complete the methods of the JobSequencer class so that all operations are as efficient as possible. The purpose of this class is to process jobs of different types in the order that they are added to the system. Because there are a limited number of job handlers and they are specialized for a particular job type, you must make sure that the "get" methods only return jobs of the requested type. You must also ensure that jobs of a particular type are processed in the order in which they arrived. You should assume that both the "add" and the "get" methods may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a short interaction with the JobSequencer class that illustrates the desired functionality: 

    >>> seq = JobSequencer()
    >>> seq.add_job("A", 101)
    >>> seq.add_job("B", 105)
    >>> seq.add_job("A", 93)
    >>> seq.add_job("B", 202)
    >>> print(seq.next_job("A"))
    101
    >>> print(seq.next_job("B"))
    105
    >>> print(seq.next_job("B"))
    202
    >>> print(seq.next_job("A"))
    93

You can test your implementation by executing job_tests.py in the same folder as your completed solution. This script will run some tests for correctness as well as timing tests. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Event Sequencer

Begin by downloading the following files:

Complete the methods of the EventSequencer class so that all operations are as efficient as possible. The purpose of this class is to store events that are tagged with an integer time stamp and then to return those events in strict chronological order: once an event with a particular time stamp has been retrieved, it should not be possible to retrieve an event with an ealier time stamp, even if this means that some events are discarded. You should assume that both the "add" and the "get" methods may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a short interaction with the EventSequencer class that illustrates the desired functionality: 

    >>> seq = event_sequencer.EventSequencer()
    >>> seq.add_event(0, "A") # Event "A" at time 0.
    >>> seq.add_event(4, "C")
    >>> seq.add_event(2, "B")
    >>> print(seq.get_next_event())
    A
    >>> print(seq.get_next_event())
    B
    >>> seq.add_event(1, "e")
    >>> seq.add_event(3, "f")
    >>> seq.add_event(5, "g")
    >>> print(seq.get_next_event()) # Won't be "e", because it occurs before "B"
    f
    >>> print(seq.get_next_event())
    C
    >>> print(seq.get_next_event())
    g

You can test your implementation by executing event_tests.py in the same folder as your completed solution. This script will run some tests for correctness as well as timing tests. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Tournament Bracket

Begin by downloading the following files:

Complete the methods of the TournamentBracket class so that all operations are as efficient as possible. The purpose of this class is to store and process results for any single-elimination bracket-style tournament. Results are added to the bracket game-by-game in the form of winner/loser pairs. Given two teams, the class should be able to determine whether the first team is "stronger" than the second team, where "stronger" is defined as follows: team A is stronger than team B if 1) team A has directly beaten team B, or if 2) team A has beaten third team that is stronger than team B. You should assume that both the "add" and the "stronger" methods may be called arbitrarily many times and in any order: efficiency matters for both.

Here is a short interaction with the TournamentBracket class that illustrates the desired functionality: 

    >>> from tournament_bracket import TournamentBracket
    >>> bracket = TournamentBracket()
    >>> bracket.add_result("Blue", "Red")
    >>> bracket.add_result("Red", "Green")
    >>> bracket.stronger("Blue", "Red")
    True
    >>> bracket.stronger("Blue", "Green")
    True
    >>> bracket.stronger("Green", "Red")
    False

You can test your implementation by executing tournament_tests.py in the same folder as your completed solution. This script will run some tests for correctness as well as timing tests. Your goal is to pass all correctness tests with an overall execution time that is as small as possible.

Submission

There is nothing to turn in immediately for this lab. Make sure you keep a copy of your code for future reference and submission. If you would like to discuss your solution or any problems you encounter while working on this lab, please come to office hours or make an appointment.