Use Python 3.6 or above. Use a text editor sensitive to whitespace like Notepad++, gedit, vim,
Sublime Text, and NOT Notepad / WordPad. The following exercises are suggestive in nature.
1. The Interpreter as a calculator. Basic arithmetic operations. Introduction to the simple
numeric data types – integers, floating point numbers, Boolean, complex numbers.
Inter conversion of data types.
a. Use the Python prompt as a basic calculator. Explore the order of operations
using parentheses.
b. Explore the various functions in the math module. Eg: find GCD of two
numbers, area and perimeter of circle using math.pi, etc.
c. Exploring the complex data type and their operations, eg: finding the modulus
and phase angle of a complex number.
d. The print function – Printing values. Repeat the previous experiments now
using the print function
2. Basic user interactions using the print() and input() functions.
a. Write a simple python script using the print function in a text editor, save it
with the extension “.py”. Run it in the terminal / command prompt.
b. Take input two strings from the user, and print the first one twice, and the
other one thrice.
c. Ask the user to enter two numbers, and output the sum, product, difference,
and the GCD.
d. More programs that test concepts learned in week 1 which involves the usage
of the print and input functions.
3. Strings, List, Tuples, the re (regular expression) module
a. Ask the user for two strings, print a new string where the first string is
reversed, and the second string is converted to upper case. Sample strings:
“Pets“, “party”, output: “steP PARTY”. Only use string slicing and +
operators.
b. From a list of words, join all the words in the odd and even indices to form
two strings. Use list slicing and join methods.
c. Simulate a stack and a queue using lists. Note that the queue deletion
operation won’t run in O(1) time.
d. Explore the ‘re’ module, especially re.split, re.join, re.search and re.match
methods.
4. Conditionals, looping constructs, and generators
a. Use list comprehension to find all the odd numbers and numbers divisible by
3 from a list of numbers.
b. Using while loops to do Gaussian addition on a list having an even number of
numbers. Print each partial sum. Eg: if the list is [1, 2, 3, 4, 5, 6], the program
should output “1 + 6”, “2 + 5”, and “3+4” in separate lines, and the result of
the addition “21”. Extend it to handle lists of odd length.
c. Primarily testing using for and while loops.
d. Use (c) to generate a list of primes within a user-given range.
e. Explore the ‘key’ function of sum( ), min( ), max( ), and sort( ) functions
using lambdas.
5. User defined functions
a. Implement popular sorting algorithms like quick sort and merge sort to sort
lists of numbers.
b. Implement the Pascal’s triangle.
c. Three positive integers a, b, and c are Pythagorean triples if a2+ b2 =c2. Write
a function to generate all Pythagorean triples in a certain range.
d. Write two functions that simulate the toss of a fair coin, and the roll of an
unbiased ‘n’ sided die using the random module.
e. Like (d), but now the coin and the die are not fair, with each outcome having
a given probability.
6. File handling, sys, pickle and csv modules
a. Basic file operations. Explore the different file modes.
b. Emulate the unix ‘cp’, ‘grep’, ‘cat’ programs in Python. In each case, the user
should pass the arguments to the program as command line arguments.
c. Use pickle for persistent storage of variables
7. Sets and dictionaries
a. Use sets to de-duplicate a list of numbers, and a string such that they contain
only the unique elements
b. Use the set union and intersection operations to implement the Jaccard and
Cosine similarity of two sets.
c. Use dictionaries to count the word and letter occurrences in a long string of
text.
d. Invert a dictionary such the previous keys become values and values keys.
Eg: if the initial and inverted dictionaries are d1 and d2, where d1 = {1: ‘a’, 2:
‘b’, 3: 120}, then d2 = {‘a’: 1, 2: ‘b’, 120: 3}.
e. What if the values in (d) are not immutable? Use frozensets. For repeated
values, use lists. Eg: if d1 = {1: ‘a’, 2: ‘a’, 4: [1, 2]}, then d2 = {‘a’: [1, 2],
frozenset([1, 2]): 4}.
f. Write a function to generate the Fibonacci numbers in (a) exponential time
using the naïve algorithm, and (b) in linear time using dynamic programming
(memorization) with a dictionary.
8. Object Oriented Programming
a. Create a ‘Graph’ class to store and manipulate graphs. It should have the
following functions:
i. Read an edge list file, where each edge (u, v) appears exactly once in
the file as space separated values.
ii. Add and remove nodes and edges
iii. Print nodes, and edges in a user readable format
iv. Computes basic statistics of the graph like degree distribution,
clustering coefficient, and the number of connected components.
v. Finding all the neighbors of a node
vi. Finding all the connected components and storing them as individual
Graph objects inside the class
vii. Finding single source shortest paths using Breadth First Search
b. Make a ‘DiGraph’ class to handle directed graphs which inherits from the
‘Graph’ class. In addition to all of the functionalities of (a), it should support
the following operations
i. Finding the predecessors and successors of a node
ii. Creating a new ‘DiGraph’ object where all the edges are reversed.
iii. Finding the strongly connected components
c. Extend (a) and (b) to handle weighted graphs, and implement Dijkstra’s and
Floyd-Warshall algorithms to compute the single source and all pairs shortest
paths.
d. Use the graph containers in (a), (b), and (c) to implement additional graph
algorithms.
No comments:
Post a Comment