Cookies disclaimer

I agree Our site saves small pieces of text information (cookies) on your device in order to deliver better content and for statistical purposes. You can disable the usage of cookies by changing the settings of your browser. By browsing our website without changing the browser settings you grant us permission to store that information on your device.

Amortized

This is the task corresponding to exercise 4. Amortized.

Resources

Download Files

Definitions File

theory Defs
  imports Main
begin

declare [[names_short]]
declare Let_def[simp]

(* Definitions *)
type_synonym 'a stk = "('a list * 'a list)"

definition empty :: "'a stk" where
  "empty \<equiv> ([],[])"

fun push :: "'a \<Rightarrow> 'a stk \<Rightarrow> 'a stk" where
  "push x (xs,ys) = (x#xs,ys)"

definition balance :: "'a list \<Rightarrow> 'a stk" where
  "balance xs = (let n = length xs div 2 in (take n xs, rev (drop n xs)))"

fun pop_fst :: "'a stk \<Rightarrow> 'a stk" where
  "pop_fst (x#xs,ys) = (xs,ys)"
| "pop_fst ([],ys) = balance (drop 1 (rev ys))"

fun pop_lst :: "'a stk \<Rightarrow> 'a stk" where
  "pop_lst (xs,y#ys) = (xs,ys)"
| "pop_lst (xs,[]) = balance (butlast xs)"

(* Timings *)
definition T_push :: "'a \<Rightarrow> 'a stk \<Rightarrow> int" where
  "T_push x stk = 1"

fun T_pop_fst :: "'a stk \<Rightarrow> int" where
  "T_pop_fst (x#xs,ys) = 1"
| "T_pop_fst ([],ys) = int (length ys)"

fun T_pop_lst :: "'a stk \<Rightarrow> int" where
  "T_pop_lst (xs,y#ys) = 1"
| "T_pop_lst (xs,[]) = int (length xs)"

consts \<Phi> :: "'a stk \<Rightarrow> int"

end

Template File

theory Submission
  imports Defs
begin

fun \<Phi> :: "'a stk \<Rightarrow> int" where
  "\<Phi> _ = undefined"

lemma \<Phi>_ge_0: "\<Phi> (xs,ys) \<ge> 0"
  sorry

lemma \<Phi>_empty_0: "\<Phi> empty = 0"
  sorry

lemma T_push: "T_push x (xs,ys) + \<Phi> (push x (xs,ys)) - \<Phi> (xs,ys) \<le> c\<^sub>1"
  oops

lemma T_pop_fst: "T_pop_fst (xs,ys) + \<Phi> (pop_fst (xs,ys)) - \<Phi> (xs,ys) \<le> c\<^sub>2"
  oops

lemma T_pop_lst: "T_pop_lst (xs,ys) + \<Phi> (pop_lst (xs,ys)) - \<Phi> (xs,ys) \<le> c\<^sub>3"
  oops

end

Check File

theory Check
  imports Submission
begin

lemma \<Phi>_ge_0: "\<Phi> (xs,ys) \<ge> 0"
  by (rule Submission.\<Phi>_ge_0)

lemma \<Phi>_empty_0: "\<Phi> empty = 0"
  by (rule Submission.\<Phi>_empty_0)

end

Terms and Conditions