Description
• One-day assignments (solving 1 problem) should ideally be completed within
the lab itself. The actual duration of the deadline is 8am on Friday to 8am on
Saturday, but the assignment is “doable” within the duration of the lab.
• Take-home assignments (solving 2 problems) should be completed before the
deadline (2 weeks per take-home assignment)
Lab Structure
• 1
st part of labs (max. 30 min): short lesson
• Cover answers for the previous session’s assignments (one-day, and take-home,
where applicable)
• Cover relevant Java API for the session’s given topic
• Brief discussion of the one-day assignment
• 2
nd part of labs: solving the one-day assignment (graded)
• The first 20-30 minutes of this part will be used for students to plan how to solve the
assignment, and express it in terms of pseudocode
• Allowed to discuss at algorithm level with other students, but no discussing/sharing
of code
• Type out the pseudo-code for your solution, which has to be shown to the TAs
• Can continue working on the assignment after the lab if necessary
Kattis Introduction
• Online platform used for submitting and grading assignments
• Found at https://nus.kattis.com/
Kattis Introduction – Signing Up
Kattis Introduction – Signing Up
Kattis Introduction – Signing Up
• Can sign up using email, or through linking to
Facebook/Google/LinkedIn
• For name, please use your name as on LumiNUS, but only capitalize
the first letter
• Eg. if your name on IVLE is “CHEN JIN XIONG, RYAN” (not a real student, as far as I
can tell) then use “Chen Jin Xiong, Ryan” (ie, do not change the ordering)
• There is currently no way to edit an account name once it has been
created, so be careful
Kattis Introduction – Registering for CS2040
Kattis Introduction – Registering for CS2040
Registration Code = cs2040_2021_s2_ckf
Kattis Introduction – Assignments
All problem sets will appear here
(bottom of the course page)
Kattis Introduction – Assignments
Click on the letter to access
the problem (only visible
when session opens)
Lab 1 – Runtime Analysis
• In CS2040, sometimes having a program/algorithm give the correct answer
may not be sufficient; it may be required that your program/algorithm
should run quickly as well
• Kattis provides the maximum running time for a program in the problem
description on the right, under “CPU Time limit”
• Generally, machines on Kattis can run close to 100 million operations a
second
• Try calculating whether your program can pass the time limit based off its
time complexity
• Eg for a problem where N <= 1000, and the time limit is 1 sec, at max value
of N (1000): N3 = 1 billion = probably not okay (> 100 million), whereas N2 =
1 million = okay
Lab 1 – Runtime Analysis
• Also note that the methods provided by Java API may not run in O(1) time,
and as such your program may run slower than intended if this is not taken
into consideration
• To fully understand the methods provided by the API, it is recommended to
read up the documentation
• The following slides are based off the Java 8 API documentation:
https://docs.oracle.com/javase/8/docs/api/
• Documentation of the later versions of Java (up to Java 10) follows the same idea,
but uses a different layout by default. To view them in the same manner, click on
“FRAMES” at the top of the page
• Documentation from Java 11 onwards does not seem to support frames, requiring
manual navigation of the packages (or just search for the class name via Google, or
the search bar at the upper right of the Java API page)
Lab 1
– Reading Java API
Package
window: can
click on them to
view only
classes from a
single package
Class window:
click on one of
them to view
the full API of
that class
Main window:
shows all the
details of the
selected class
Lab 1 – Reading Java API
• For the package window, clicking on a package will switch the class
window to show only the classes in that package
• Frequently used packages are:
• java.util
• Almost everything that’s covered later in the module
• java.lang
• Strings and related classes
• Wrapper classes
• java.io
• Buffered input/output (covered in a later lab)
• For Java 9 onwards, these are found under the java.base package in the
documentation (but retain the same package names otherwise)
Lab 1 – Reading Java API
• For the main window, the contents tend to be sorted as follows:
• 1. Brief description of class
• 2. Fields, constructors and methods (short version, sorted alphabetically)
• Click on an entry here to go to the relevant entry in section 3
• 3. Fields, constructors and methods (long version, may not be sorted)
• The time complexity of a method will sometimes be stated in section
1 or 3
Lab 1 – Useful API
• Scanner class – used for reading input
• Found in the java.util package; need to use the following line to
import:
• import java.util.*;
• Declare a new Scanner object with the following line (in main
method):
• Scanner sc = new Scanner(System.in);
• Read in input using the methods found in Scanner:
• int testCases = sc.nextInt();
Lab 1 – Scanner
Method name Description Time
.nextInt() Reads the next token in the input as an integer O(n)
.nextDouble() Reads the next token in the input as a double O(n)
.next() Reads the next token in the input as a String O(n)
.nextLine() Reads until it reaches the end of the line O(n)
n refers to the length of the input that is read
These slides covering API will cover the most frequently used (but not all) methods of a class;
for a full list, refer to the Java API documentation
Lab 1 – System.out (not really a class)
Method name Description Time
System.out.print(String str) Prints str O(n)
System.out.println(String str) Prints str, followed by a newline character (‘\n’) O(n)
System.out.printf(String format,
Object… args)
Emulates the printf function from C O(n)
Technical note: System.out is an instance of the PrintStream class, so you may refer to the API documentation
on PrintStream (in java.io) to explore more methods
n is the length of the output
Lab 1 – Useful API
• String class – contains several methods that could be of use
• Found in the java.lang package; is imported by default
• Can be constructed in various ways:
• String str1 = new String(“apple”);
• String str2 = “apple”;
• char[] arr = {‘a’, ‘p’, ‘p’, ‘l’, ‘e’};
• String str3 = new String(arr);
Lab 1 – String
Method name Description Time
.split(String delim) Splits a String into an array of Strings, based off the characters
found in delim
O(length of
string)
.charAt(index i) Returns the character at index i (0-based) O(1)
.equals(String other) Checks if this string has the same value as the value of String
other
Note: not the same as using ==
O(length of
shorter
string)
.concat(String other) Returns a new string which is this string + other
Note: does not modify the original String (Strings are immutable
in Java)
O(length of
resulting
string)
.length() Returns the length of the string O(1)
.substring(int start, int end) Returns a new string, which contains the content of the original
string from index start (inclusive) to index end (exclusive)
(indices are 0-based)
O(length of
resulting
string)
Lab 1 – Command Line/Terminal Usage
• It is helpful to know how to compile and execute Java programs via
command line (example below)
Lab 1 – Command Line/Terminal Usage
• cd ../../test
• “cd” is the command used to move between folders. “..” means to go up one
folder
• dir
• Used to list the contents of a folder. Use “ls” (lowercase L, lowercase S) on
Unix-like systems
• javac Echo.java
• “javac” is the command use to compile Java programs. The full file name
(inclusive of “.java”) is required, and seeing no output is a good thing.
• Each class in the Java file is compiled to its own “.class” file
Lab 1 – Command Line/Terminal Usage
• java Echo < Hello.txt
• java Echo < HelloDouble.txt
• “java” is the command used to run compiled Java programs. No filename
extension (.java, .class) should be provided
• “<“ followed by the name of a file is used to provide input from a file (known
as input redirection).
Instead of having to type out your input manually; simply save your input in a
file and use “<“ to avoid retyping input each time you test your program
One-Day Assignment 0 – Pea Soup
• First one-day assignment; is ungraded
• Found at https://nus.kattis.com/problems/peasoup
• Future assignments will be found on the main Kattis course page at
https://nus.kattis.com/courses/CS2040/CS2040_S2_AY2021 (at the
bottom of the page).
• Writing pseudocode for this assignment is not necessary, but will be
required from the next one-day assignment onwards
One-Day Assignment 0 – Pea Soup
• Given a list of restaurants, and their menus, determine the first
restaurant appearing in the list that offers both “pea soup” and
“pancakes”
• Should be the exact strings “pea soup” and “pancakes”; even if a
menu item contains the substring “pea soup” or “pancakes”, ignore it
(see Sample Input 2)
Assignment Guidelines
• Important: Include your name and student number in comments at
the top of your code
• Rehash of “IMPORTANT Rules for CS2040 Assignments” file:
• If you discuss the problem with any other student(s), include their
name(s) as collaborators in a comment at the top of your code
• No usage of anyone else’s code (outside of code provided in lecture
materials)
• Directly using (eg. copy-paste) is not allowed
• Using code as a reference is not allowed either
