Tutorial 5
Introduction to
Computer Science
01
Quick Revision
Lists
• Represent a collection of data
Representation:
Position/Index 0 1 2 3 4
Value 12 34 8 6 1
• My_list[0] = 12
• My_list[3] = 6
Lists
• Represent a collection of data
Reading Elements:
• A=[5, -9, 4, 3]
• print(A[0]) -> 5
• Print(A[len(A) - 1]) -> 3
• Print(A[len(A)]) -> error (index out of range)
Lists
• Represent a collection of data
Creation:
• My_list = [1,2,3] #List of Integers
• My_list= [] #Empty List
• My_List = [1, “hello”, 3.4] #List of mixed data
• My_list = eval(input(“enter your list”))
User enters: [1, 2, 4] # [1, 2, 4] vs 1,
2, 4
Lists
• Represent a collection of data
Functions
• len(my_list) : Gets the length of the list
Note: first position is always 0, last position is length-1
02
Excercises
01
Mysterious Task
Trace the following program with the following inputs
ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11]
while b > a + 1:
ar = eval(input()) mid = (a + b) // 2
a=0 if (ar[a] - a) != (ar[mid] - mid):
b = len(ar) - 1 b = mid
mid = 0 elif (ar[b] - b) != (ar[mid] - mid):
a = mid
print(ar[mid] + 1 if ar[mid]+1!=ar[mid+1] else ar[mid] - 1)
01
Mysterious Task
What is the functionality of the program ?
while b > a + 1:
ar = eval(input()) mid = (a + b) // 2
a=0 if (ar[a] - a) != (ar[mid] - mid):
b = len(ar) - 1 b = mid
mid = 0 elif (ar[b] - b) != (ar[mid] - mid):
a = mid
print(ar[mid] + 1 if ar[mid]+1!=ar[mid+1] else ar[mid] - 1)
02
Print Repeated
Write an algorithm that given an ordered list of integers A prints the elements in the
list that are
repeated. If some elements occur more than twice, then these elements should be
printed only once.
For example, for the list:
111146778
your algorithm should print
17
02
Print Repeated
Write an algorithm that given an ordered list of integers A prints the elements in the
list that are
repeated. If some elements occur more than twice, then these elements should be
printed only once.
list_A = eval(input())
n = len(list_A)
i=0
printed = False
while i < n - 1:
if (list_A[i] != list_A[i+1]):
printed = False
else:
if printed == False:
print(list_A[i])
printed = True
i=i+1
03
362 Pattern
Write an algorithm that given a list of integers A displays True if the list contains a 3,
6, 2 pattern. A 3, 6, 2 pattern is a value, followed directly by the value plus 3, followed
directly by the value minus 1.
Here are some examples of evaluating the algorithm on representative input values:
• [1, 3, 6, 2] --> True
• [1, 2, 7, 1] --> False
• [3, 6, 2] --> True
• [4, 7, 3] --> True
• [5, 8] --> False
• [1, 3, 6, 2, 5, 1] --> True
Your algorithm should stop whenever the pattern is found.
03
362 Pattern
Solution :
A = eval(input())
i=0
flag = False
n = len(A)
while(i < n-2):
if(A[i+1] - A[i] == 3 and A[i+2] - A[i] == -1):
flag = True
break
i += 1
print(flag)
04
Occurrence Counter
Given a list of (in increasing order) sorted positive integers and an integer k, write a
Python program that finds all elements occurring at least k times in the list.
For example:
Input: 1, 3, 4, 4, 4, 7, 7, 8
k=2
Output: 4 7
Explanation: 4 occurs 3 times and and 7 occurs 2 times.
Input: 1, 3, 4, 4, 7, 7, 8
k=3
Output: None
Note: You are not allowed to use more than one loop. You should traverse the list only
once.
04
Occurrence Counter
Solution :
list = eval(input())
k = eval(input()) while(i<len(list)-1):
i=0 if(list[i]==list[i+1]):
c=1 c += 1
flag = False if(c==k):
print(list[i])
flag = True
else:
c=1
i+=1
if(flag == False):
print("none")
Any
Questions ?!